14.1 事务概念

构成单一逻辑工作单元的操作集合称作事务。

数据库系统必须以一种能够避免引入不一致性的方式来管理实务的并发执行。

因为事务是不可分割的，所以要么执行其全部内容，要么就根本不执行。这个称作原子性(Atomicity)。

数据库必须采取特殊处理来确保事务正常执行而不被来自并发执行的数据库语句所干扰。这种特性称为隔离性(Isolation)。尽管多个事务可能并发执行，但系统保证，对于任何一对事务$T_i$和$T_j$，在$T_i$看来，$T_j$或者在$T_i$开始之前已经完成执行，或者在$T_j$完成之后开始执行。因此，每个事务都感觉不到系统中有其他事务在并发执行。

即使系统能保证一个事务的正确执行，如果此后系统崩溃，结果系统“忘记”了该事务，那么这项工作的意义也不大了。因此，即使崩溃后事务的操作也必须是持久的。这种特性称为持久性(Durability)。

这三个构成了构造与数据库的交互的一种理想方式。还有一个特性叫做一致性(Consistency)。如何实现这个则是编写事务的程序员的职责。

14.2 一个简单的事务模型

保证原子性的基本思路如下：对于事务要执行写操作的数据项，数据库系统在磁盘上记录其旧值。这个信息记录在一个称为日志的文件中。如果事务没能完成它的执行，在数据库系统从日志中恢复旧值，使得看上去事务从未执行过。保证原子性是数据库系统本身的责任。

持久性的保证可以使用下面的两条中的任何一条来保证：

• 事务做的更新在事务结束前已经写入磁盘
• 有关事务已执行的更新信息已写到磁盘上，并且此类信息必须充分，能让数据库在系统出现故障后重新启动时重新构造更新。

事务的并发执行是有可能导致数据库系统的不一致的。一种避免事务并发执行而产生问题的途径是串行地执行事务–一个接一个地执行。但是这个方法不符合性能要求。事务的隔离性确保事务并发执行后的系统状态与这些事务以某种次序一个接一个地执行后的状态是等价的。确保隔离性是数据库系统中称作并发控制系统的部件的责任。

14.3 存储结构

易失性存储器

比如主存储器和高速缓冲存储器。

非易失性存储器

比如二级存储设别磁盘和闪存，三级存储设备光介质和磁带。

稳定性存储器

理论上是一个永远不会丢失的存储设备。可以通过复制非易失性存储器来组成。为了一个事务能够持久，它的修改应该写入稳定性存储器。同样，为了一个事务是原子的。日志记录需要在对磁盘上的数据库做任何改变之前写入稳定性存储器。

14.4 事务原子性和持久性

事务并不是总能成功，没有成功的事务的状态，叫做事务的终止状态。一旦中止事务造成的变更被撤销，我们就说事务已回滚。恢复机制负责事务中止，典型的方法是维护一个日志。每个事务对数据库的修改都首先会记录到日志中。我们记录执行修改的事务标识符、修改的数据项标识符以及数据项的旧值和新值。然后数据库才会修改。成功完成执行的事务称为已提交。一个对数据库进行过更新的已提交事务使数据库进入一个新的一致状态，即使出现故障，这个状态也得保持。

补偿事务用来撤销一个已提交事务。这个是由用户来控制的。

• 活动的：初始状态，事务执行时处于这个状态。
• 部分提交的：最后一条语句执行后
• 失败的：发现正常的执行不能继续后
• 中止的：事务回滚并且数据库已恢复到事务开始执行前的状态后
• 提交的：成功完成之后

部分提交和已提交的区别

事务从活动状态开始。当事务完成它的最后一个条语句后就进入了部分提交状态。此刻，事务已经完成它的最后一条语句后就进入了部分提交状态。此刻，事务已经完成执行，但由于实际输出可能仍临时驻留在主存储器中，因此一个硬件故障可能阻止其成功完成。于是事务仍有可能不得不中止。接着数据库系统往磁盘上写入足够的信息，确保即使出现故障时事务所做的更新也能在系统重启后重新创建。

外部可见的写

在处理外部可见的写的时候，大多数系统只允许这种写操作在事务进入提交状态后发生。实现这种模式的一种方法是在非易失性存储设备中临时写下与外部写相关的所有数据，然后在事务进入提交状态后再执行真正的写操作。如果在事务进入提交状态后而外部写操作尚未完成之前，系统出现了故障，数据库系统就可以在重启后执行外部写操作了。有的时候重启应该执行一个补偿操作，比如外部写是支付现金，因为人可能已经走了。

14.5 事务隔离性

两个允许并发的理由：

• 提高吞吐量和资源利用率
• 减少等待时间，可以减少平均响应时间。

数据库必须控制事务之间的交互，以防止它们破坏数据库的一致性。系统通过称为并发控制机制的一系列机制来保证这一点。

一个由n个指令组成的事务，有n!个调度方案。并发情况下并不是所有的调度组合都可以正确执行从而得到一个最终一致的状态。

如果让操作系统来控制事务的并发执行，那么许多调度都是可能的，那么就可能会让数据库处于不一致的状态。因此保证所执行的任何调度都能使数据库处于一致状态，这是数据库系统的任务，数据库中完成此任务的是并发控制部件。

在并发执行中，通过保证所执行的任何调度的效果都与没有并发执行的调度效果一样，我们可以确保数据库的一致性。也就是说调度应该在某种意义上等价于一个串行调度。这种调度称为可串行化调度。

14.6 可串行化

冲突可串行化

对于一个调度S，其中有分别属于$I$和$J$的两条连续指令$I_i$和$J_j$。如果$I$和$J$引用了不同的数据项，则交换它们不会影响调度中任何指令的结果。然而，如果它们引用了相同的数据项$Q$，则两者的顺序是重要的。现在只考虑有read和write指令，则有下面4种情形：

• $I=read(Q)$,$J=read(Q)$。那么它们的次序没有关系。
• $I=read(Q)$,$J=write(Q)$。那么它们的次序是有关系的。
• $I=write(Q)$,$J=read(Q)$。那么它们的次序是有关系的。
• $I=write(Q)$,$J=write(Q)$。那么它们的次序是有关系的。

只有当两个操作都为read(Q)的时候或者引用不同的数据项，它们的次序才是没有关系的。也就是它们是无冲突的。当一个调度S可以经过调换一系列无冲突的连续指令（属于不同事务）的执行顺序后得到了一个新的调度$S \prime$，那么这两个调度之间是冲突等价的。

并不是所有的串行调度之间都是冲突等价的。将两个事务完全调换顺序，就有可能不是冲突等价的。

如果一个调度S与一个串行调度是冲突等价的，那么调度S是冲突可串行化的。

如何判断一个调度是冲突可串行化的

考虑下表中的一个调度7

$T_3$	$T_4$
read(Q)
	write(Q)
write(Q)

可以由调度构造一个有向图，称为优先图。

边$T_i \rightarrow T_j$的存在只有在下列三个条件中的一个成立了：

• 在$T_j$执行read(Q)之前，$T_i$执行了write(Q)
• 在$T_j$执行write(Q)之前，$T_i$执行read(Q)
• 在$T_j$执行write(Q)之前，$T_i$执行了write(Q)

也就是有冲突的指令，都是$T_i$先执行时。如果优先图有环，则这个调度是非冲突可串行化，如果优先图无环，则这个调度是冲突可串行化。

存在比冲突等价定义限制松一些的调度等家定义。

14.7 事务隔离性和原子性

调度除了要考虑一致性以外，还要考虑事务的故障恢复。

14.7.1 可恢复调度

一个事务在读取了另一个在活跃状态写入的一个值之后，提交了自己。则说明前者依赖后者。如果活跃状态的事务进入了中止状态，而这个事务已经提交了，无法恢复了。这就是一个不可恢复的调度。

一个可恢复调度应该满足：对于每对事务$T_i$和$T_j$，如果$T_j$读取了$T_i$所写的数据项，则$T_i$要优先于$T_j$提交。

14.7.2 无级联调度

即使一个调度是可恢复的，要从事务$T_i$的故障中正确恢复，可能需要回滚若干事务。

比如事务$T_8$写入A的值，事务$T_9$读取了A的值。事务$T_9$写入A的值，事务$T_10$读取了A的值。如果$T_8$事务失败，$T_8$则必须回滚，由于$T_9$依赖于$T_8$，因此事务$T_9$必须回滚。同样$T_10$也因为$T_9$而回滚了。这种因单个事务故障导致一系列事务回滚的现象称为级联回滚。

但是级联回滚会导致大量的撤销工作，因此我们希望避免级联回滚发生。这样的调度称为无级联调度。

一个无级联调度应满足：对于每对事务$T_i$和$T_j$，如果$T_j$读取了先前由$T_i$所写的数据项，那么$T_i$必须在$T_j$这一读操作前提交。这个调度也必然是可恢复调度。

14.8 事务隔离性级别

对于某些应用，保证可串行性的那些协议可能只允许极小的并发度。在这种情况下，我们采用较弱级别的一致性。为了保证数据库的正确性，使用弱级别一致性给程序员增加了额外的负担。

SQL标准也允许一个事务以一种与其他事务部可串行化的方式执行。例如一个事务可能在未提交读级别上操作，这里允许事务读取甚至还未提交的记录。SQL为那些不要求精确结果的长事务提供这种特征。如果这些事务要在可串行化的方式下执行，它们就会干扰其他事务，造成事务执行的延迟。

SQL标准规定的隔离性级别如下。

• 可串行化：通常保证可串行化调度。
• 可重复读：只允许读取已提交数据，而且在一个事务两次读取一个数据项期间，其他事务不得更新该数据。例如，当一个事务在查找满足某些条件的数据时，它可能找到一个已提交事务插入的一些数据，但可能找不到该事务插入的其他数据。
• 已提交读：只允许读取已提交数据，但不要求可重复读。
• 未提交读：允许读取未提交数据。这是SQL允许的最低一致性级别。

以上所有隔离性级别都不允许脏写，即如果一个数据项已经被另外一个尚未提交或中止的事务写入，则不允许对该数据项执行写操作。

许多数据库系统运行时的默认隔离性级别时已提交读。有些数据库虽然在隔离性上设置为可串行化，但实际上数据库可能仍然采用了较弱的隔离性。

隔离性级别的实现

并发控制机制的目的是获得高度的并发性、同时保证所产生的调度是冲突可串行化或视图可串行化的、可恢复的，并且是无级联的。

并发控制的实现

14.9.1 锁

共享锁和排他锁。共享锁用于读事务，排他锁用于事务写的数据项。许多事务可以同时持有一个数据项上的共享锁。当且只有当其他事务在一个数据项上不持有任何锁时，一个事务才能持有它的排他锁。这两种锁结合两阶段锁封锁协议在保证可串行化的前提下允许数据的并发读。

14.9.3 时间戳

通常在事务开始的时候为它分配一个时间戳，对于数据项，系统维护两个时间戳。数据项的读时间戳记录该数据项的事务的最大（最近的）时间戳。数据项的写时间戳记录写入该数据项当前值的事务的时间戳。

14.9.3 多版本和快照隔离

通过维护数据项的多个版本，一个事务允许读取一个旧版本的数据项。有许多多版本并发控制技术，其中一个是实际中广泛应用的称为快照隔离的技术。不会让写操作等待。

14.10 事务的SQL语句表示

比如select ID,name from instructor where salary > 90000;，如果有人插入了一个新的人，那么查询的结果就会取决于插入和查询的执行顺序了。这称为幻象。简单模型是无法发现这个冲突的。因为它要求提供一个具体的数据项作为操作的参数。还有一个是谓词锁，封锁一些具体的更新动作。